package LeetCodeHot100TopInterview;

import java.util.Arrays;

public class Q322_CoinChange {
    //给定不同面额的硬币 coins 和一个总金额 amount
    //编写一个函数来计算可以凑成总金额所需的最少的硬币个数
    //如果没有任何一种硬币组合能组成总金额，返回-1
    //你可以认为每种硬币的数量是无限的

    //找零问题 普通币版
    //直接 dp 就完事
    //都衍生自背包问题
    //方案数  硬币个数 ? ==> 不好复用
    //硬币个数 == 这种做法了解一下
    public int coinChange(int[] arr, int money) {

        if (arr == null || arr.length == 0) {
            return 0;
        }

        //0 -> money
        //dp[n] 代表 搞定 n 金额的最小硬币
        int[] dp = new int[money + 1];
        //默认dp[0] = 0;
        //没有就返回 -1
        //money 代表不可能换取的数量 因为下面进行比对用 min 函数 可以被淘汰
        Arrays.fill(dp, money + 1);
        dp[0] = 0;

        for (int i = 1; i <= money; i++) {
            for (int j = 0; j < arr.length; j++) {
                //不用 || 用
                if (i - arr[j] >= 0)
                    //不用就是搞定 i 金额最小的货币  用就是搞定(i - 当前币值) + 当前币
                dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1) ;
            }
        }
        return dp[money] == (money + 1) ? -1 : dp[money];
    }

    public static void main(String[] args) {
        Q322_CoinChange fun = new Q322_CoinChange();
        System.out.println(fun.coinChange(new int[]{1, 2, 5}, 11));
    }
}
